Goldreich-Levin theorem

Theorem (Goldreich-Levin)

If $f$ is a one-way function, then $g(x,r) = (f(x),r)$ is also a one-way function and $hc(x,r) = \langle x,r \rangle = \sum (x_i \cdot r_i) (\mod 2)$ is a hard-core predicate of $g$.

Notes

• allows constructing PRG from any one-way permutation

References

1. https://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture7.pdf
2. https://www.ccs.neu.edu/home/wichs/class/crypto-fall15/lecture8.pdf
3. https://cs.stanford.edu/people/trevisan/pacc/lecture9.pdf
4. https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture6.pdf